package com.itcrx.binarySearch;

/**
 * @author NoobMaster69  * @date 2024/5/28 0028 星期二 19:41
 */
public class BinarySearch {

    /**
     * 二分查找基础
     * @param a 带查找的升序数组
     * @param target 带查找的目标值
     * @return 找得到返回索引 找不到返回 -1
     */
    public int binarySearchBasic(int[] a , int target){
        int i = 0,j = a.length - 1; //设置两个指针和初值
        while (i <= j){ //范围内还有值
            int m = (i + j) >>> 1;  //解决超过int的表示范围
            if(target < a[m]){  //目标值在左标，所以a[m]的右边不考虑
                j = m - 1;
            }else if(a[m] < target){  //目标值在右标
                i = m + 1;
            }else {
                return m;
            }
        }

        return -1;
    }

    /**
     * 二分查找改良版
     * @param a 带查找的升序数组
     * @param target 带查找的目标值
     * @return 找得到返回索引 找不到返回 -1
     */
    public int binarySearchAlternative(int[] a , int target){
        int i = 0,j = a.length;
        while (i < j){
            int m = (i + j) >>> 1;
            if(target < a[m]){
                j = m;
            }else if(a[m] < target){
                i = m + 1;
            }else {
                return m;
            }
        }

        return -1;
    }

    /**
     * 二分查找平衡版
     * @param a 带查找的升序数组
     * @param target 带查找的目标值
     * @return 找得到返回索引 找不到返回 -1
     */
    public int binarySearchPh(int[] a , int target){
        int i = 0,j = a.length - 1;
        while (i <= j){
            int m = (i + j) >>> 1;
            if(target < a[m]){
                j = m;
            }else {
                i = m;
            }
        }
        if(a[i] == target){
            return i;
        }else {
            return -1;
        }

    }

    /**
     * 二分查找     Leftmost
     * @param a 带查找的升序数组
     * @param target 带查找的目标值
     * @return 找得到返回索引 找不到返回 -1
     */
    public int binarySearchLeftmost1(int[] a , int target){
        int i = 0,j = a.length - 1; //设置两个指针和初值
        int candidate = -1;
        while (i <= j){ //范围内还有值
            int m = (i + j) >>> 1;  //解决超过int的表示范围
            if(target < a[m]){  //目标值在左标，所以a[m]的右边不考虑
                j = m - 1;
            }else if(a[m] < target){  //目标值在右标
                i = m + 1;
            }else {
                //记录候选者位置
                candidate = m;
                j = m -1;
            }
        }
            return candidate;
    }

    /**
     * 二分查找     Rightmost
     * @param a 带查找的升序数组
     * @param target 带查找的目标值
     * @return 找得到返回索引 找不到返回 -1
     */
    public int binarySearchRightmost(int[] a , int target){
        int i = 0,j = a.length - 1; //设置两个指针和初值
        int candidate = -1;
        while (i <= j){ //范围内还有值
            int m = (i + j) >>> 1;  //解决超过int的表示范围
            if(target < a[m]){  //目标值在左标，所以a[m]的右边不考虑
                j = m - 1;
            }else if(a[m] < target){  //目标值在右标
                i = m + 1;
            }else {
                //记录候选者位置
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    public int tt(int[] nums , int target){
        int i = 0,j = nums.length - 1,candidate = -1;
        while(i <= j){
            int mid = (i + j) >>> 1;
            if(target < nums[mid]){
                j = mid - 1;
            }else if(nums[mid] < target){
                i = mid + 1;
            }else {
                candidate = mid;
                j = mid - 1;
            }
        }
        return candidate;
    }

}
